package class05_归并排序练习题快排.test;

/**
 * 非递归快排
 */
public class Code03_QuickSortRecursiveUnRecursive {
    public static void quickSort1(int[] arr){
        if(arr == null || arr.length < 2){
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    private static void process(int[] arr, int L, int R) {
        if(L >= R){
            return;
        }
        int[] part = partition(arr, L, R);
        process(arr, L, part[0]);
        process(arr, part[1], R);
    }

    private static int[] partition(int[] arr, int l, int r) {
        if(l > r){
            return new int[]{-1, -1};
        }
        if(l == r){
            return new int[]{l, l};
        }

        int p = l - 1;
        int p2 = r + 1;
        int index = l;
        while (index < p2){
            if(arr[index] < arr[r]){
                swap(arr, index++, ++p);
            }else if(arr[index] > arr[r]) {
                swap(arr, index, --p2);
            }else {
                index++;
            }
        }
        return new int[]{p, p2};
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5,3,1,2,5,77,88,44,33,22,999};
        quickSort1(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);

        }
    }
}
